package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

/**
 * <a href="https://leetcode-cn.com/problems/binary-tree-inorder-traversal/">
 * 94. 二叉树的中序遍历</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 *
 * @author or2
 * @date 2021年10月12日 时间: 12:15
 */
public class No94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null)
            return Collections.emptyList();

        var stack = new LinkedList<TreeNode>();
        var res = new LinkedList<Integer>();

        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty())
                break;
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }

        if (ThreadLocalRandom.current().nextInt(12) == 2) {
            System.gc();
            try {
                Thread.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return res;
    }
}
